package com.njupt.backtracking;

import java.sql.Array;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/15 16:26
 * @Description: 93. 复原 IP 地址
 * @Version: 1.0
 */


public class RestoreIpAddresses_93 {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder(s);
        int startIndex = 0;
        int pointNum = 0;
        traceBacking(startIndex,pointNum,result,sb);
//        traceBacking1(startIndex,result,s,sb);
        return result;
    }

    private void traceBacking1(int startIndex, List<String> result, String s, StringBuilder sb) {
        if(startIndex == s.length()){
            sb.deleteCharAt(sb.length()-1);
            result.add(sb.toString());
            sb.append('.');
            return;
        }
        if(countPoint(sb)  && startIndex<s.length()){
            return;
        }

        for (int i = startIndex; i <s.length() ; i++) {
            if(isStringValid(s,startIndex,i)){
                sb.append(s.substring(startIndex,i+1));
                sb.append('.');
                traceBacking1(i+1,result,s,sb);
                sb.deleteCharAt(sb.length()-1);
                int i1 = sb.lastIndexOf(".");
                if(i1>0){
                    sb.delete(i1,sb.length());
                }
            }else {
                break;
            }
        }
    }

    private boolean isStringValid(String s, int start, int end) {
        if(start>end){
            return  false;
        }
        if(s.charAt(start) == '0' && start<end){
            return false;
        }
        Long num = Long.valueOf(s.substring(start, end + 1));
        if(num>255){
            return false;
        }
        return true;

    }

    private boolean countPoint(StringBuilder sb) {
        int count = 0;
        for (int i = 0; i < sb.length(); i++) {
            if(sb.charAt(i) == '.'){
                count++;
                if(count == 4){
                    return true;
                }
            }
        }
        return false;
    }

    private void traceBacking(int startIndex,int pointNum, List<String> result, StringBuilder sb) {

        if(pointNum == 3){
            if(isValid(sb,startIndex,sb.length()-1)){
                result.add(sb.toString());
            }
        }

        for (int i = startIndex; i < sb.length(); i++) {
            if(isValid(sb,startIndex,i)){
                sb.insert(i+1,'.');
                pointNum++;
                traceBacking(i+2,pointNum,result,sb);
                sb.deleteCharAt(i+1);
                pointNum--;
            }else {
                break;
            }
        }
    }

    private boolean isValid(StringBuilder s, int start, int end) {

        if(start>end){
            return false;
        }
        if(s.charAt(start) == '0' && start<end){
            return false;
        }
        Long num = Long.valueOf(s.substring(start, end + 1));
        if(num>255){
            return false;
        }
        return true;
    }


    public static void main(String[] args) {
        String s = "25525511135";
        RestoreIpAddresses_93 test = new RestoreIpAddresses_93();
        List<String> results = test.restoreIpAddresses(s);
        for (String str :results){
            System.out.println(str);
        }

        Set<List<Integer>> set = new HashSet<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);

        List<Integer> list2 = new ArrayList<>();
        list2.add(1);
        list2.add(2);
        list2.add(3);
        set.add(list1);
        set.add(list2);
        System.out.println(set);

    }

}
